package hl.alde;

public class ActivityArrange {

        /*
        解决方案代码：
        i    表示 第i个活动
        s[i] 表示 第i个活动的开始时间
        f[i] 表示 第i个活动的结束时间
        a[i] 是否选择安排第i个活动（true代表是，false代表否）
        */
        public static void greedySelector(int[] s, int[] f, boolean[] a)
        {
            a[1] = true;		// 选择安排活动1
            int j = 1;		// 记录最近一次的活动序号
            int count = 1;		// 总的可以安排的活动数

            int n = s.length - 1;
            for(int i=2; i<=n; i++)	// 依次检查其余每一项活动与已选择的活动的相容性
            {
                if(s[i] >= f[j])	// 如果第i项活动相容
                {
                    a[i] = true;	// 选择安排第i项活动
                    j = i;		// 记录最近一次的活动序号
                    count++;	// 总的可以安排的活动数加1
                }
                else			// 如果不相容
                    a[i] = false;	// 选择不安排第i项活动
            }

            // 打印 活动安排情况，安排的数量
            for (int i=1; i<a.length; i++)
                System.out.println("A" + i + " = " + a[i]);
            System.out.println("总的活动数量 = " + count);
        }

        public static void main(String[] args)
        {
		    // 定义11项活动的开始时间，结束时间（按升序排序）
            int[] s = {0,1,3,0,5,3,5,6, 8, 8, 2, 12};// s[0]不用
            int[] f = {0,4,5,6,7,8,9,10,11,12,13,14};// f[0]不用
            boolean[] a = new boolean[12];// a[0]不用

            // 调用贪心算法 安排活动 并 计算最大可安排数量
            greedySelector(s, f, a);

        }
}
